The standard video compression algorithms (ISO MPEG, ITU H.261/263) use block-based motion compensation to exploit the temporal redundancy inherent in video data and to achieve compression. When the best match falls within the local search window of the reference frame, usually the immediately previous frame, the standard algorithms offer satisfactory compression ratios. However, if a good match can not be found in the reference frame, which very often occurs in video with high motion content, then a very high coding cost would have to be paid for the subject block. This is known as the non-locality disaster.
A new global motion compensation method is developed in the present invention to overcome the non-locality disaster. This method makes use of the information of the immediately previous frame as well as the information in all the previous frames in history. The present invention also makes use of information outside the conventional local search window.
Motion compensation is an important step in all video compression. The standard (H.261/263, MPEG) motion compensation algorithms employ a block-based strategy, where all the possible macroblocks in the local window of the reference frame are searched for the best match of each macroblock in the current frame. A second method of motion compensation found in some nonstandard algorithms apply global motion estimation and luminance invariance coding. The global motion estimation is the process to detect the potential global motions in the reference frame, create a new reference frame using global motion compensation, and predict the current frame based on this new reference frame. This global motion estimation method is usually helpful for dealing with camera movement such as pan, tilt, and zoom. Luminance invariance coding detects the same scene under different lighting conditions. Once luminance invariance is detected, the reference frame is warped to make it closer to the current frame.
Digital video content with high motion and change in large spatial scales is becoming more and more popular in new generation multimedia applications. Typical examples include video captured from sporting and entertainment events, from commercial materials, and from synthetic productions. A statistical majority of this high motion or “large change” content can not be effectively classified and treated using the techniques an methods described above.
The present invention restates the motion compensation objective as a vector quantization problem. Namely, if the subject macroblock (a square of 16×16 luminance values) is a 256-dimensional vector, then the local search window in the reference frame serves as a codebook for coding this macroblock. In this context, the best match represents the hit entry in the codebook and the motion vector represents the codeword—indexed to the codebook—under consideration.
In this conception, prior art motion compensation techniques can be properly characterized as a local codebook approach to vector quantization. That is to say that the codebook for coding the subject macroblock is built upon the information of a local window of the reference frame. It is spatially local because only a relatively small window in the reference frame is considered, and it is temporally local because only the immediately previous frame is referred to. This local codebook approach has two major limitations. First, when large motion changes occur in adjacent frames, the best match may fall outside of the relatively small local searching window. Secondly, this approach is unable to make use of a good match that may be found in a historically previous frame that is not the immediately previous frame. When any of these situations occurs, a high computing cost is paid for coding the subject block thus “the non-locality disaster”.
The present invention improves upon the exclusively local codebook approach by building a codebook based on all the possible macroblocks in all temporally previous frames. Theoretically, this extension can be done by simply including more previous frames as reference and by enlarging the search window in those reference frames. As an extreme case, reference range can be as long as the whole history of the encoded sequence, and the search window can be of the size of the entire frame. However, this conceptually simple solution is unaffordable from computation cost viewpoint.
The present invention, may be called Global Codebook Aided Motion Compensation or GCAMC. GCAMC represents a simple and efficient method and system to make use of the spatial and temporal information of previously coded macroblocks. In the present invention, the information regarding previously coded macroblocks is quantized and saved in a global codebook, and the global codebook is updated dynamically in both the encoding and decoding environments. A dual, comparative motion compensation process is performed using both the local search window and the global codebook. This allows the coding system both to take advantage of the local codebook should there be little motion and to make use of information in the global codebook if the change is dramatic.
The principal objective of the present invention is to provide a new method and a system for the compression coding and decompression of digital video content with high motion and dramatic content changes.
This background information is provided for the purpose of making known information believed by the applicant to be of possible relevance to the present invention. No admission is necessarily intended, nor should be construed, that any of the preceding information constitutes prior art against the present invention.